КНФ и СКНФ

**Конъюнктивная нормальная форма (КНФ)** — это формула вида $\bigwedge_{i=1}^{n} F_{i},~ n \geqslant 1$, где $F_{i} = \bigvee_{j=1}^{k_{i}} L_{ij}$, $L_{ij}$ — литерал, $k_{i} \geqslant 1$. $F_{i}$ называют **элементарными дизъюнкциями** или **клозами** (clause). КНФ — тоже **иерархическая** формула: отрицание применяется только к переменным, дизъюнкция — к литералам, конъюнкция — к клозам.

КНФ от $k$ переменных называется **совершенной ($k$-СКНФ)**, если: * все клозы $F_{i}$ различны; * каждый $F_{i}$ состоит из $k$ литералов, соответствующих различным переменным.